package com.wangjie.doublepointer;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author jieshao
 * @date 2022/4/25 14:11
 *
 * 870. 优势洗牌(田忌赛马加强版)
 *
 * 将齐王和田忌的马按照战斗力排序，然后按照排名一一对比，如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的来送人头，保存实力
 */
public class Test05 {
    public static void main(String[] args) {
        int[] nums1 = {2, 7, 11, 15};
        int[] nums2 = {1, 10, 4, 11};
        int[] res = advantageCount(nums1, nums2);
        System.out.println("res:" + Arrays.toString(res));
    }

    /**
     * 我们需要对两个数组排序，但是 nums2 中元素的顺序不能改变，因为计算结果的顺序依赖 nums2 的顺序，所以不能直接对 nums2 进行排序，而是借助
     * PriorityQueue 优先级队列来辅助
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        // nums2 降序
        PriorityQueue<int[]> queue = new PriorityQueue<>((int[] pair1, int[] pair2) -> pair2[1] - pair1[1]);
        for (int i = 0; i < n; i++) {
            // 数组中有两个元素，第一个元素为数组的索引，第二个元素为数组的值
            queue.offer(new int[]{i, nums2[i]});
        }
        // nums1 升序
        Arrays.sort(nums1);
        // nums1[left] 是最小值，nums1[right] 是最大值
        int left = 0;
        int right = n - 1;
        int[] res = new int[n];
        while (!queue.isEmpty()) {
            int[] pair = queue.poll();
            // i 是 nums2 的索引
            int i = pair[0];
            // value 是 nums2 索引对应的值
            int value = pair[1];
            if (value < nums1[right]) {
                // 如果 nums1[right] 大于 value，那就自己上
                res[i] = nums1[right];
                right--;
            } else {
                // 否则用最小值混⼀下，养精蓄锐
                res[i] = nums1[left];
                left++;
            }
        }
        return res;
    }
}